package leetcode_1801_1900;

public class LeeCode_1894 {
    public static void main(String[] args) {
        System.out.println(chalkReplacer(new int[]{5, 1, 5}, 22));
        System.out.println(chalkReplacer(new int[]{3,4,1,2}, 25));
    }
    private static int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] sums = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + chalk[i - 1];
        }
        k %= sums[n];
        return search(sums, k) - 1;
    }
    private static int search(long[] sums, int goal){
        int l = 0, r = sums.length - 1;
        while (l < r){
            int m = (l + r) / 2;
            if (sums[m] <= goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        return l;
    }
}
